#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	int val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;


BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->val = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreatTree()
{
	BTNode* Node1 = BuyNode(1);
	BTNode* Node2 = BuyNode(2);
	BTNode* Node3 = BuyNode(3);
	BTNode* Node4 = BuyNode(4);
	BTNode* Node5 = BuyNode(5);
	BTNode* Node6 = BuyNode(6);
	BTNode* Node7 = BuyNode(7);

	Node1->left = Node2;
	Node1->right = Node4;
	Node2->left = Node3;
	Node4->left = Node5;
	Node4->right = Node6;
	Node3->right = Node7;

	return Node1;
}

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}


void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

void LevelOrder(BTNode* root)
{

}

int TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}


int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);

	return left > right ? left + 1: right + 1;
}

int LevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int left = LevelKSize(root->left, k - 1);
	int right = LevelKSize(root->right, k - 1);

	return left + right;
}

int main()
{
	BTNode* root = CreatTree();
	PrevOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	PostOrder(root);
	printf("\n");

	int size = TreeSize(root);
	printf("TreeSize: %d\n", size);

	int height = TreeHeight(root);
	printf("TreeHeight: %d\n", height);

	int ksize = LevelKSize(root, 3);
	printf("%dlevelSize: %d\n", 3, ksize);

	printf("%dlevelSize: %d\n", 4, LevelKSize(root, 4));
	printf("%dlevelSize: %d\n", 2, LevelKSize(root, 2));
	printf("%dlevelSize: %d\n", 1, LevelKSize(root, 1));

	return 0;
}
